package org.example;

public class Test1 {
    //leetcode 最小覆盖字串
    // https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-interview-150
    public String minWindow(String s, String t) {
        int n1 = s.length(), n2 = t.length();
        int left = 0, right = 0;
        int[] hash1 = new int[58], hash2 = new int[58];
        int type1 = 0; //记录t有多少种字符
        int ret = 100001, start = 0, end = 0;
        for (char c : t.toCharArray()) {
            if (hash1[c-'A']++ == 0) type1++;
        }
        int count = 0; // 记录窗口有效的单词的个数
        int type2 = 0; // 记录窗口中有效的字母的种类
        while (right < n1) {
            char tmp = s.charAt(right);
            hash2[tmp-'A']++;
            if (hash1[tmp-'A'] > 0) {
                if (hash2[tmp-'A'] == hash1[tmp-'A']) type2++;
                count++;
            }
            right++;
            //表示窗口中的字符串已经是t的覆盖字串了
            while (type2 == type1) {
                //看是否是最小覆盖子串
                if (right - left < ret) {
                    ret = right - left;
                    start = left;
                    end = right;
                }
                char leftStr = s.charAt(left);
                hash2[leftStr-'A']--;
                if (hash1[leftStr-'A'] > 0) {
                    if (hash2[leftStr-'A'] < hash1[leftStr-'A']) type2--;
                    count--;
                }
                left++;
            }
        }
        return ret == 100001 ? "" : s.substring(start, end);
    }
}
